[기수정렬] 백준 10989번

문제

오름차순으로 정렬하시오
(첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.)

문제분석

입력의 수의 범위가 많으므로, 일반적인 정렬은 선택하는데에 시간초과의 가능성이 존재한다
기수 정렬을 이용하여 (O(KN)), 메모리 사용을 주의하며 작성

기수정렬 방식

• 자릿수별로 Queue를 이용하여, 정렬하고 이후 정렬될 숫자의 최대 자릿수만큼 반복하며 정렬하는 방식
• 시간복잡도 : O(KN) , K는 최대 자릿수

정렬 수 :	60	12	20	45	30	75	32	88	99
30, 20, 60		32, 12			75, 45			88	99
0	1	2	3	4	5	6	7	8	9
일의 자리 정렬 :	60	20	30	12	32	45	75	88	99
	12	20	32, 30	45		60	75	88	99
0	1	2	3	4	5	6	7	8	9
십의 자리 정렬 :	12	20	30	32	45	60	75	88	99

• 일의 자릿수 끝났을 때 -> 일의자리수 정렬이 되있음 (따라서, 60 - 20 - 30 은 일의자리만 비교했기에, 정렬이 되지 않은상태로 저장)
• 십의 자릿수 끝났을 때 -> 십의자리 + 일의자리 정렬이 되있음
• 백의 자리수 끝났을 때 -> 백의자리 + 십의자리 + 일의자리 정렬이 되있음

기수정렬 구현

• 문제에서 숫자의 최대크기를 제한했으므로, 메모리를 해당 수 이하만큼 돌면 되므로 max_size를 설정하여 기수정렬을 풀이하면된다.
  • getMax()로 배열의 최대값을 구해 자릿수를 계산하는 방식은 배열 전체를 한 번 더 순회해야 하므로 시간 초과가 발생한다. 문제 조건에서 수의 최대값이 10,000(5자리)임을 알 수 있으므로, max_size를 5로 고정해 불필요한 순회를 없애야 한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class App {
 
    public static void radixSort(int[] arr, int max_size){
        
        int[] output = new int[arr.length];
 
        int exp = 1;
        int count = 0;
        while(count != max_size){
            
            int[] sumArray = new int[10];
 
            //자릿수에 맞춰서 저장
            for(int i = 0; i< arr.length; i++){
                sumArray[(arr[i]/exp)%10]++;
            }
 
            //합 배열 구하기
            for(int i = 1; i<10; i++){
                sumArray[i] += sumArray[i-1];
            }
            
            // output에 저장하는 인덱스가 해당 범위의 끝부터 저장하기에 큰수부터 넣어야한다 (그래서 반복문을 arr.length-1부터)
            for(int i = arr.length-1; i >= 0 ; i--){
                int digit = (arr[i]/exp)%10;
                output[sumArray[digit] - 1] = arr[i];
                sumArray[digit]--;
            }
 
            for(int i = 0; i<arr.length; i++){
                arr[i] = output[i];
            }
            
            exp = exp*10;
            count++;
        }
    }
    
    public static void main(String[] args) throws IOException {
 
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int arr_size = Integer.parseInt(bf.readLine());
        int[] arr = new int[arr_size];
        for(int i =0; i< arr_size; i++){
            arr[i] = Integer.parseInt(bf.readLine());
        }
        bf.close();
        radixSort(arr,5);
        for (int i : arr) {
            bw.write(i +"\n");
        }
 
        bw.flush();
        bw.close();
    }
    
}

---

관련 문서

• [정렬] 기수정렬 — 이 문제에 적용된 기수정렬 개념 설명